public class Offer12 {
    public boolean exist(char[][] board, String word) {
        if (word==null||board==null||board.length<1||board[0].length<1) return false;
        boolean[][] hasVisited= new boolean[board.length][board[0].length];
        int pathLength = 0;

        for (int row = 0; row < board.length; row++) {
            for (int col = 0; col < board[0].length; col++) {
                if (rollback(board,row,col,pathLength,hasVisited,word)){
                    return true;
                }
            }
        }
        return false;
    }
    public boolean rollback(char[][] board,int row,int col,int pathLength,boolean[][] hasVisited,String word){
        if (pathLength==word.length()) return true;
        boolean hasPath = false;
        if (row< board.length&&row>=0&&
        col<board[0].length&&col>=0&&
        !hasVisited[row][col]&&word.charAt(pathLength)==board[row][col]){
            pathLength++;
            hasVisited[row][col]=true;
            hasPath = rollback(board,row,col-1,pathLength,hasVisited,word)||
                    rollback(board,row,col+1,pathLength,hasVisited,word)||
                    rollback(board,row-1,col,pathLength,hasVisited,word)||
                    rollback(board,row+1,col,pathLength,hasVisited,word);

            if (!hasPath){
                hasVisited[row][col]=false;
                pathLength--;
            }
        }
        return hasPath;
    }
}
